package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/5/2 14:03
 */
public class C125 {

    // 相对i位置开始往外扩, 从range为区间开始尝试, 返回最后扩到的右边界
    private static boolean expand(char[] str, int i) {
        int l, r = -1;
        for (int range = 1; (r = i + range) < str.length && (l = i - range) > -1; range++) {     // 不管怎样先让右边界都+range, 管他哪儿边现超r都已经+上了
            if (str[l] != str[r]) {
                return false;
            }
        }
        return true;
    }

    // 转成manacher字符串, 模拟扩
    public static boolean isPalindrome(String s) {
        s = s.toLowerCase();
        char[] s1 = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        for (char c : s1) {
            if( (c >= '0' && c <= '9') || (c >='a' && c <= 'z') ) sb.append('_').append(c);
        }
        char[] str = sb.append('_').toString().toCharArray();
        return expand(str, str.length >> 1);
    }


    // 左右指针
    public static boolean isPalindrome2(String s) {
        s = s.toLowerCase();
        char[] str = s.toCharArray();
        int l = 0, r = str.length-1;
        while (l < r) {
            if( !( (str[l] >= '0' && str[l] <= '9') || (str[l] >='a' && str[l] <= 'z') ) ) {
                l++;
            }else if( !( (str[r] >= '0' && str[r] <= '9') || (str[r] >='a' && str[r] <= 'z')) ) {
                r--;
            }else {
                if(str[l++] != str[r--]) return false;
            }
        }
        return true;
    }

    // for test
    public static void main(String[] args) {
        String s = "raceacar";
        System.out.println(isPalindrome(s));
        System.out.println(isPalindrome2(s));
    }

}
